AnthonyAAAAA

个人主页
修改帐号
退出

昵称：AnthonyAAAAA

等级：没等级

文章：0

下次自动登录

登录
注册

找回密码

首页
版面收藏夹
版面目录
精华区收藏夹
关注/粉丝

3

MDog

六点勺园约么？

凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数凑字数

Anniversary

未名BBS 2018明信片册和巨型鼠标垫限量发售

经过前期的准备，北大未名BBS 于18周年站庆之际面向全站网友推出系列纪念品。纪念品图案均为过往优秀日常进站图片，欢迎大家关注。 　　首发时间：2018年06月20日、21日（星期三、四）10:

deliver

新手上路必读

亲爱的朋友： 　　恭喜您已经通过北大未名BBS的身份认证，非常高兴您成为我们共同的大家庭中新的一员，我们将尽我们所能为您提供完善的服务！收到这封信后，退出BBS然后重新登录，就可以成为正式用户，拥有各

deliver

恭喜您完成注册单身份核验

您已经通过北大未名BBS的身份检验，我们认为您的资料已经符合要求，所以让您通过。我们非常的兴奋，又多了一位使用者加入这个大家庭，我们将会尽力为您提供最好的服务，祝愿您在本站愉快。 　　参与版面讨论

查看全部

修改帐号
偏好设置
校内认证
帮助中心
退出

算法设计与分析12年期末题回忆(转载) - 精华区 - 信息科学技术学院(EECS)版 - 北大未名BBS

首页
版面目录
一区: 北京大学
信息科学技术学院(EECS)
精华区
...
算法设计与分析
算法设计与分析12年期末题回忆(转载)

算法设计与分析12年期末题回忆(转载)

创建人：cyblocker

最后修改于 2012-06-13 16:52:16

<ASCIIArt>

发信人: cyblocker (CIS&DMP10|阿宝), 信区: EECS

标  题: 算法设计与分析12年期末题回忆(转载)

发信站: 北大未名站 (2012年06月13日16:49:23 星期三), 转信

原文由 cyblocker 发表在 CIS 版

小题不写了，选择判断什么的。。。

大题有9个，最后两个是附加题，前7个顺序不保证正确，两个附加题附参考答案（我自己

做的- -仅供参考……用来纪念最后一门算法课吧。。。）

1. 最短路径树和最小生成树

一个图上的一个最小生成树，是否一定对某一个节点u而言，沿着树到其他点是最短路径

，也就是是否是一定是某个节点u的最小路径树。（一次Dijkstra过程形成的树就是一个

最短路径树）若是，请证明；若不是，请举反例。

2. 区间最小点集

给出一大堆区间[ai,bi]，共m个（下标从1--m），求最小的点集P，使得每一个区间都包含

至少一个在P中的节点。请给出尽量优的算法，并证明算法正确性，说明时间复杂度。

3. 独立集合

给出n个集合，如{1,2}，{1,2,3}，{1,3,2}等等。给出尽量优的算法求这n个集合中的独

立集合个数。定义独立集合是指在这n个集合中只出现了一次的集合，如上例中的{1,2}是

独立集合，而{1,2,3}{1,3,2}均不是。

4. 最优三叉树

现有n堆石子，每一堆石子有ai个石子。每一次可以选取2堆或3堆进行合并，合并代价为

这两堆或三堆中的石子总数。请设计算法求最小代价，并证明算法正确性。

5. 旋转序列求最小值

给定一个数列，这个数列是将一个升序序列旋转得到的。旋转是指将序列首尾相接进行左

移或右移的操作。例如序列{3,4,5,6,1,2}是序列{1,2,3,4,5,6}旋转得到的。现要在一个

旋转后的序列中寻找最小值，请设计算法解决这一问题。并写出代码或伪代码。

6. 最大乘积子串

给定一个数字序列，请设计算法求该数列中的一个连续子序列（子串），使得他们的乘积

最大。

7. 冒泡排序

冒泡排序是一种反复通过比较相邻的元素的排序方法，若相邻元素前者大于后者则进行交

换。以下分析可以认为待排序数组中的元素各不相等。请：

(1)分析冒泡排序过程中元素被交换的概率；

(2)分析冒泡排序的期望交换次数并简要说明。

8. 队列辅助结构

队列的入队、出队时间代价为O(1)，而求最小值的代价是O(n)的，也就是必须要扫描一遍

整个队列才可以得到。请设计一个辅助的数据结构，和队列一同存在，使得总的三种操作

的平摊复杂读均为O(1)。

参考答案

设计一个辅助队列，当原队列有一个元素入队的时候，从队尾检查辅助队列，若存在元素

并队尾元素>插入的元素，则删除队尾元素，直到辅助队列为空或队尾<当前插入元素。（

保持辅助队列单调增）随后将当前元素插入队尾。出队时，检查当前元素是否==辅助队列

的队首，则辅助队列也出队。由于每个元素在辅助队列中只会入队/出队一次，所以容易

证明均摊代价为O(1)

9. 有上下界的最大流

（奖学金评选）有p个课程，m个学生，n个班级；每门课要从选课学生中评选出不少于L个

不多于H个学生获得奖学金，每个学生可以选修不限门课程，选课情况已知。每个学生只

能获得一次奖学金，每个学生属于一个班级，每个班级获得奖学金的人数不超过ai个人，

总获得奖学金的人数不能超过T个。请设计算法判断，是否存在可行的奖学金分配方案。

参考答案

建图很简单，源流到每个课程，容量限制为L-H，每个课程指向每个选课的学生，容量为

1，每个学生指向对应的班级，容量为1，班级指到一极汇点，容量为ai，一级汇点指到二

级汇点，容量为T。求限制条件下的最大流问题。上界没问题，关键在于下界L的处理。

详细介绍和论述请见NOI2006冬令营讲座 江涛的《最大流在信息学竞赛中应用的一个模型

》一文中的第六部分--无源汇的可行流问题。或周源《一种简易的方法求解流量有上下界

的网络中网络流问题》

简要描述算法如下：

下面所说的汇都是指上文中的二级汇点

添加一条边：汇指向源，流量为无穷。将原来有下界的边分离成一个必要边，容量为下界

，一个可行边，容量为上界-下界。将所有必要边的目标节点都改成一个新的附加节点X，

X指向一个附加节点Y，然后再将Y分发到原来的目标节点。（就是把所有的必要边集中到

两个中间结点去）

问题转化为从X到Y的最大流问题，若存在最大流，则存在可行解。完毕。具体证明和说明

请见上面提到的两篇文章。

--

████┐  █┐    █┐████┐    ████┐ 十一学校的各位

█┌──█┐██┐  █│█┌──█┐█┌───┘ 以及各位朋友们~~

████┌┘█┌█┐█│█│    █│└███┐   BNDS版已经成立

█┌──█┐█│└██│█│    █│  └──█┐

████┌┘█│  └█│████┌┘████┌┘ BMS:cyblocker Crandia

└───┘  └┘    └┘└───┘  └───┘   欢迎关注！

※ 来源:·北大未名站 bdwm.net·[FROM: 162.105.57.121]

--

※ 转载:·北大未名站 bdwm.net·[FROM: 162.105.57.121]

收入文集

您输入的密码有误，请重新输入

确认

常用网站 - 相关下载 - 未名站刊 - 关于我们 - 联系我们 - 加入我们 - 帮助中心 - 意见反馈

© 2000–2018 北大未名BBS

 消息

新建聊天





载入中...

搜索

复制